// hard

// 给定一个整数k和整数n，分别代表k枚鸡蛋和可以使用的一栋从第1层到第n层楼的建筑
// 已知存在楼层f，满足0 <= f <= n，任何从高于f的楼层落下的鸡蛋都会碎，从f楼层或比它低的楼层落下的鸡蛋都不会碎
// 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层x扔下，如果鸡蛋碎了，就不能再次使用它，如果鸡蛋没碎，则可以再次使用
// 要求：计算并返回要确定f确切值的最小操作次数是多少


// 解题思路1： 动态规划（超时）
// 1-n之间的任意一层扔鸡蛋
//      1. 如果鸡蛋没碎，则1-x层都不用考虑了，我们用k个鸡蛋考虑剩下的n-x层，问题就从(n,k)转变为了(n-x, k)
//      2. 如果鸡蛋碎了，则x+1 到n层都不用考虑了，我们需要用剩下的k-1个鸡蛋考虑剩下的x-1，问题就从(n, k)转变为了(x-1, k-1)
// 1. 划分阶段，按照楼层数量，剩余鸡蛋个数进行阶段划分
// 2. 定义状态，dp[i][j]表示为：一共有i层楼，j个鸡蛋的条件下，为了找出f，最坏情况下的最少扔鸡蛋次数
// 3. 状态转移方程, dp[i][j] = min(max(dp[i-x][j], dp[x-1][j-1])) + 1,  1 <= x <= n
// 4. 初始条件，给定鸡蛋k的取值范围为[1,100],f的取值范围为[0,n],初始化时，可以考虑将所有值设置为当前拥有的楼层数
//      1. 当鸡蛋数为1，dp[i][1] = i，如果唯一的蛋碎了，则无法测试了，只能从低到高，一步步进行测试，最终最少测试数为当前拥有的楼层数
//      2. 当楼层为1，在1层扔鸡蛋，dp[1][j] = 1,这是因为
//          1. 如果在1层扔鸡蛋碎了，则f < 1,因为f的取值为[0,n],所以能确定f=0
//          2. 如果在1层扔鸡蛋没碎，则f >= 1,同时因为f的取值为[0,n]，所以能确定f=0
// 5. 最终结果，dp[i][j]表示为一共有i层楼，j个鸡蛋的条件下，为了找出f，最坏情况下的最少扔鸡蛋次数，则最终结果为dp[n][k]

// 复杂度分析
// 时间复杂度：O(n^2 * k)
// 空间复杂度：O(n * k)
function superEggDrop(k, n) {
    let dp = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0))

    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < k + 1; j++) {
            dp[i][j] = i
        }
    }

    for (let j = 1; j < k + 1; j++) {
        dp[1][j] = 1
    }

    for (let i = 2; i < n + 1; i++) {
        for (let j = 2; j < k + 1; j++) {
            for (let x = 1; x < i + 1; x++) {
                dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - x][j], dp[x - 1][j - 1]) + 1)
            }
        }
    }
    return dp[n][k]
}

// 解题思路2： 动态规划优化
// 此时我们把 dp[i - x][j] 和 dp[x - 1][j - 1] 分别单独来看。可以看出：

// 对于 dp[i - x][j]：当 x 增加时，i - x 的值减少，dp[i - x][j] 的值跟着减小。自变量 x 与函数 dp[i - x][j] 是一条单调非递增函数。
// 对于 dp[x - 1][j - 1]：当 x 增加时， x - 1 的值增加，dp[x - 1][j - 1] 的值跟着增加。自变量 x 与函数 dp[x - 1][j - 1] 是一条单调非递减函数。
// 两条函数的交点处就是两个函数较大值的最小值位置。即 dp[i][j] 所取位置。而这个位置可以通过二分查找满足 dp[x - 1][j - 1] >= dp[i - x][j] 最大的那个 x。
// 这样时间复杂度就从 O(n^2*k) 优化到了O(nlogn * k) 。

// 复杂度分析
// 时间复杂度：O(nlogn * k )
// 空间复杂度：O(n * k)
function superEggDrop(k, n) {
    let dp = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0))

    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < k + 1; j++) {
            dp[i][j] = i
        }
    }

    for (let j = 1; j < k + 1; j++) {
        dp[1][j] = 1
    }

    for (let i = 2; i < n + 1; i++) {
        for (let j = 2; j < k + 1; j++) {
            let left = 1
            let right = i
            while (left < right) {
                let mid = left + Math.floor((right - left) / 2)
                if (dp[mid - 1][j - 1] < dp[i - mid][j]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            dp[i][j] = Math.max(dp[left - 1][j - 1], dp[i - left][j]) + 1
        }
    }
    return dp[n][k]
}

// 解题思路3，动态规划 + 逆向思维
// 至少需要扔几次鸡蛋才能保证无论f是多少层，都能将f找出来
// 逆向思维下，题目可以变为，已知有k个鸡蛋，最多扔x次鸡蛋，求最多可以检测多少层
// 我们把未知条件 【扔鸡蛋的次数】 变为了已知条件，将 【检测的楼层个数】变为了未知条件
// 这样如果求出来的【检测的楼层个数】大于等于n，则说明1-n层数都考虑全了，f值也就明确了，我们只需要从符合条件的情况里，找出【扔鸡蛋的次数】最少的次数即可

// 1. 划分阶段，按照鸡蛋个数，扔鸡蛋的次数进行阶段划分
// 2. 定义状态，定义状态dp[i][j]表示为，一共有i个鸡蛋，最多扔j次鸡蛋（碎不碎都算一次）的条件下，最多可以检测的楼层个数
// 3. 状态转移方程
//      我们现在有i个鸡蛋，j次扔鸡蛋的机会，现在尝试在1-n层中的任意一层x扔鸡蛋
//          1. 如果鸡蛋没碎，剩下i个鸡蛋，还有j- 1次扔鸡蛋的机会，最多可以检测dp[i][j-1]层楼层
//          2. 如果鸡蛋碎了，剩下i-1个鸡蛋，还有j-1次 扔鸡蛋的机会，最多可以检测dp[i-1][j-1]层楼层
//          3. 再加上我们扔鸡蛋的第x层，i个鸡蛋，j次扔鸡蛋的机会，最多可以检测 dp[i][j-1] + dp[i-1][j-1] + 1
//      状态转移方程为： dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1
// 4. 初始条件，当鸡蛋数位1，只有1次扔鸡蛋的机会时，最多可以检测1层，dp[1][1] = 1
// 5. 最终结果
// 根据我们之前定义的状态，dp[i][j] 表示为：一共有 i 个鸡蛋，最多扔 j 次鸡蛋（碎没碎都算 1 次）的条件下，最多可以检测的楼层个数。
// 则我们需要从满足 i == k 并且 dp[i][j] >= n（即 k 个鸡蛋，j 次扔鸡蛋，一共检测出 n 层楼）的情况中，找出最小的 j，将其返回。

function superEggDrop(k, n) {
    let dp = new Array(k + 1).fill(0).map(() => new Array(n + 1).fill(0))
    dp[1][1] = 1

    for (let i = 1; i < k + 1; i++) {
        for (let j = 1; j < n + 1; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1
            if (i === k && dp[i][j] >= n) {
                return j
            }
        }
    }
    return n
}
let k = 2, n = 6
console.log(superEggDrop(k, n))